//顺序存储的线性表

#include <stdio.h>
#include <stdlib.h>
//定义一个宏，静态数据存储满后不可存储
#define MAX 4

typedef struct List
{
    // 存储元素的数组，类型或者说存储目标（整型或其他结构体）元素类型
    //使用指针类型(定义数组)来动态分配数组空间
    int* data;
    int size;       //大小
    int capacity;   //容量
}List;
//声明的相关操作
//初始化线性表
void init(List * l);
//在末尾插入元素
void add(List* l,int e);
//在索引位置插入元素
void inser(List* l,int index,int e);
//删除索引位置的元素
int del(List* l,int index);
//查找索引位置的元素
int get(List* l,int index);
//查找值，返回索引，不存在-1
int find(List* l,int val);
//返回表的大小
int size(List* l);
//清空表
void empty(List* l);
//打印
void show(List* l);
//扩容
void grow(List * l);
int main()
{
    List* list;
    //指针初始化,list 指针，动态分配了 16 字节空间
    list = (List*)malloc(sizeof(List));

    //初始化线性表
    init(list);
    show(list);
    for(int i = 0;i< 10;i++)
    {
        add(list,i);
    }
    show(list);

    // add(list,100);
    // add(list,200);
    // // show(list);
    // add(list,300);
    // add(list,400);
    // // show(list);
    // inser(list,2,666);
    // show(list);
    // del(list,4);
    // show(list);
    // int getindex = get(list,2);
    // printf("%d\n",getindex);
    // int index = find(list,555);
    // printf("%d\n",index);
    // int index1 = find(list,200);
    // printf("%d\n",index1);
    // int size1 = size(list);
    // printf("%d\n",size1);
    // empty(list);
    return 0;
}
void grow(List * l)
{
    //线性表满了
    if(l->size == l->capacity)
    {

        //扩容时增量大小为多少的策略
        // 1）* 2
        // 2）* 1.5
        // 3）+ N
        //增量大小
        // << n 就是 * 2^n 
        // >> n 就是除以2的n次方，因为性能好一点
        int incr = l->capacity >> 1;
        //增量就是原始容量
        l->capacity += incr;
        printf("扩容：容量%d, 大小：%d\n",l->capacity,l->size); 
        //动态内存分配
        printf("扩容前地址: %p\n",l->data);
        l->data = (int*)realloc(l->data,l->capacity *sizeof(int));
        printf("扩容后地址: %p\n",l->data);
    }

}
//O(n)
void inser(List* l,int index,int e)
{
    //TODO
    //是否扩容
    if(index == l->size)
    {
        add(l,e);
    }
    if(index < l->size)
    {
        for(int i = l->size -1;i>=index;i--)
        {
            l->data[i+1] = l->data[i];
        }
        //将新数据存入目标位置
        l->data[index] = e;
        l->size++;
    }
}
// O(n)
int del(List* l,int index)
{
    int val = l->data[index];
    // index +1 覆盖 index
    for(int i = index;i< l->size-1;i++)
    {
        l->data[i] = l->data[i+1]; 
    }
    l->size--;
    return val;
}
//O(1)
void init(List * l)
{
    l->capacity = MAX;
    l->size = 0;
    // data 创建一块连续的存储空间，可以存储4个元素
    l->data = malloc( l->capacity * sizeof(int));
}
//O(1)
void add(List* l,int e)
{
    // 是否满了
    //TODO
    //扩容，条件若不成立，不调用函数，减少空间浪费
    if(l->size == l->capacity)
        grow(l);

    l->data[l->size] = e;
    l->size++;
}
//O(n)
void show(List* l)
{
    printf("------------------------------------\n");
    printf("线性表：");
    for(int i = 0;i<l->size;i++)
    {
        printf("%d ",l->data[i]);
    }
    printf("\n容量：%d,大小：%d\n",l->capacity,l->size);
    printf("------------------------------------\n");

}
//O(1)
int get(List* l,int index)
{
    //是否越界
    return l->data[index];
}
//O(n)
int find(List* l,int val)
{
    // for(int i = 0;i<l->size;i++)
    // {
    //     if(l->data[i] == val)
    //     {
    //         return i;
    //     }
    // }
    // return -1;
    
    int index= -1;
    for(int i = 0;i<l->size;i++)
    {
        if(l->data[i] == val)
        {
            index = i; 
            break;
        }
    }
    return index;
}
//O(1)
int size(List* l)
{
    return l->size;
}
//O(1)
void empty(List* l)
{
    l->size = 0;
    free(l);
    l = NULL;
}
